{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Rectangle Enclosing Black Pixels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #binary-search #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #二分查找 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minArea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #包含全部黑色像素的最小矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>图片在计算机处理中往往是使用二维矩阵来表示的。</p>\n",
    "\n",
    "<p>给你一个大小为 <code>m x n</code> 的二进制矩阵&nbsp;<code>image</code> 表示一张黑白图片，<code>0</code>&nbsp;代表白色像素，<code>1</code>&nbsp;代表黑色像素。</p>\n",
    "\n",
    "<p>黑色像素相互连接，也就是说，图片中只会有一片连在一块儿的黑色像素。像素点是水平或竖直方向连接的。</p>\n",
    "\n",
    "<p>给你两个整数 <code>x</code> 和 <code>y</code> 表示某一个黑色像素的位置，请你找出包含全部黑色像素的最小矩形（与坐标轴对齐），并返回该矩形的面积。</p>\n",
    "\n",
    "<p>你必须设计并实现一个时间复杂度低于&nbsp;<code>O(mn)</code> 的算法来解决此问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/14/pixel-grid.jpg\" style=\"width: 333px; height: 253px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>image = [[\"0\",\"0\",\"1\",\"0\"],[\"0\",\"1\",\"1\",\"0\"],[\"0\",\"1\",\"0\",\"0\"]], x = 0, y = 2\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>image = [[\"1\"]], x = 0, y = 0\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == image.length</code></li>\n",
    "\t<li><code>n == image[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 100</code></li>\n",
    "\t<li><code>image[i][j]</code> 为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "\t<li><code>1 &lt;= x &lt; m</code></li>\n",
    "\t<li><code>1 &lt;= y &lt; n</code></li>\n",
    "\t<li><code>image[x][y] == '1'</code></li>\n",
    "\t<li><code>image</code> 中的黑色像素仅形成一个 <strong>组件</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-rectangle-enclosing-black-pixels](https://leetcode.cn/problems/smallest-rectangle-enclosing-black-pixels/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-rectangle-enclosing-black-pixels](https://leetcode.cn/problems/smallest-rectangle-enclosing-black-pixels/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"0\",\"0\",\"1\",\"0\"],[\"0\",\"1\",\"1\",\"0\"],[\"0\",\"1\",\"0\",\"0\"]]\\n0\\n2', '[[\"1\"]]\\n0\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        m, n = len(image), len(image[0])\n",
    "        min_x, max_x = x, x\n",
    "        min_y, max_y = y, y\n",
    "        q, head = [[x, y]], -1\n",
    "        visited = set((x, y))\n",
    "        while head < len(q) - 1:\n",
    "            head += 1\n",
    "            for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                xx, yy = q[head][0] + d[0], q[head][1] + d[1]\n",
    "                if xx < 0 or xx >= m or yy < 0 or yy >= n:\n",
    "                    continue\n",
    "                if (xx, yy) in visited or image[xx][yy] != \"1\":\n",
    "                    continue\n",
    "                q.append([xx, yy])\n",
    "                visited.add((xx, yy))\n",
    "                min_x = min(min_x, xx)\n",
    "                max_x = max(max_x, xx)\n",
    "                min_y = min(min_y, yy)\n",
    "                max_y = max(max_y, yy)\n",
    "        return (max_x - min_x + 1) * (max_y - min_y + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        # 方法1:尬做法。未利用到x,y\n",
    "        m = len(image)\n",
    "        n = len(image[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                image[i][j] = int(image[i][j])\n",
    "        rowMark = [False for i in range(m)]\n",
    "        colMark = [False for j in range(n)]\n",
    "        for i in range(m):\n",
    "            if sum(image[i]) != 0:\n",
    "                rowMark[i] = True\n",
    "        for j in range(n):\n",
    "            tempSum = 0\n",
    "            for i in range(m):\n",
    "                tempSum += image[i][j]\n",
    "            if tempSum != 0:\n",
    "                colMark[j] = True \n",
    "        \n",
    "        p1 = 0\n",
    "        p2 = m - 1\n",
    "        while p1 < m and rowMark[p1] != True:\n",
    "            p1 += 1\n",
    "        while p2 >= 0 and rowMark[p2] != True:\n",
    "            p2 -= 1\n",
    "        deltaM = abs(p1-p2)+1\n",
    "\n",
    "        p3 = 0\n",
    "        p4 = n - 1\n",
    "        while p3 < n and colMark[p3] != True:\n",
    "            p3 += 1\n",
    "        while p4 >= 0 and colMark[p4] != True:\n",
    "            p4 -= 1\n",
    "        deltaN = abs(p3-p4)+1\n",
    "        return deltaM * deltaN\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        L = float(\"inf\")  # 左 left\n",
    "        R = float(\"-inf\")  # 右 right\n",
    "        T = float(\"inf\")  # 上 top\n",
    "        B = float(\"-inf\")  # 下 bottom\n",
    "        row = len(image)\n",
    "        col = len(image[0])\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if image[r][c] == \"1\":\n",
    "                    L = min(L, c)\n",
    "                    R = max(R, c)\n",
    "                    T = min(T, r)\n",
    "                    B = max((B, r))\n",
    "\n",
    "        return abs(R - L + 1) * abs(B - T + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        m, n = len(image),len(image[0])\n",
    "        minX,minY,maxX,maxY = x, y, x, y\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if image[i][j]==\"1\":\n",
    "                    minX=min(minX, i)\n",
    "                    maxX=max(maxX, i)\n",
    "                    minY=min(minY, j)\n",
    "                    maxY=max(maxY, j)\n",
    "        return (maxX-minX+1)*(maxY-minY+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        # 二分法\n",
    "        # 基础是只在有必要的时候进行二分\n",
    "        # 需要四次二分，关键在于二分区间初始值的设定\n",
    "        m = len(image)\n",
    "        n = len(image[0])\n",
    "\n",
    "        # case1\n",
    "        left = 0\n",
    "        right = x\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            state = False \n",
    "            for element in image[mid]:\n",
    "                if element == \"1\": # 这一行存在1，\n",
    "                    state = True\n",
    "                    break \n",
    "            if state: # 这一行存在1，收缩right\n",
    "                right = mid - 1 # 收缩right,可能收缩过头，但是返回的是left所有没有关系\n",
    "            if not state: # 这一行不存在1，收缩left\n",
    "                left = mid + 1        \n",
    "        upLimit = left # \n",
    "\n",
    "        # case2\n",
    "        left = x\n",
    "        right = m-1\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            state = False \n",
    "            for element in image[mid]:\n",
    "                if element == \"1\": # 这一行存在1，收缩left  \n",
    "                    state = True \n",
    "                    break \n",
    "            if state: # 这一行存在1，收缩left\n",
    "                left = mid + 1\n",
    "            if not state:\n",
    "                right = mid - 1\n",
    "        downLimit = right\n",
    "\n",
    "        # case3\n",
    "        left = 0\n",
    "        right = y\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            state = False \n",
    "            for i in range(m):\n",
    "                if image[i][mid] == \"1\": # 这一列存在1，收缩right\n",
    "                    state = True \n",
    "                    break \n",
    "            if state:\n",
    "                right = mid - 1 # # 收缩right,可能收缩过头，但是返回的是left所有没有关系\n",
    "            if not state:\n",
    "                left = mid + 1\n",
    "        leftLimit = left \n",
    "\n",
    "        # case4\n",
    "        left = y\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            state = False \n",
    "            for i in range(m):\n",
    "                if image[i][mid] == \"1\": # 这一列存在1，收缩left \n",
    "                    state = True \n",
    "                    break \n",
    "            if state:\n",
    "                left = mid + 1\n",
    "            if not state:\n",
    "                right = mid - 1\n",
    "        rightLimit = right\n",
    "\n",
    "        # print(upLimit,downLimit,leftLimit,rightLimit)\n",
    "        return (abs(upLimit-downLimit)+1) * (abs(leftLimit-rightLimit)+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    mid =  height / width = (row[-1] - row[0]) /(col[-1] - col[0])\n",
    "    left = 1\n",
    "    right = m / n \n",
    "    situation 1: if mid is too big, row[-1] - row[0] >= black height or col[-1] - col[0] >= black width\n",
    "    situation 2: if mid is too small,  row[-1] - row[0] < black height or col[-1] - col[0] < black width\n",
    "\n",
    "    '''\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        # find black height\n",
    "        height, width = self.find_black(image, x, y)\n",
    "\n",
    "        # # # find height\n",
    "        # left = 0\n",
    "        # right = len(image) - 1 # row\n",
    "\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "\n",
    "        #     if mid >= black_height:\n",
    "        #         right = mid - 1\n",
    "        #     else:\n",
    "        #         left = mid + 1\n",
    "        \n",
    "        # height = left \n",
    "\n",
    "        # left = 0\n",
    "        # right = len(image[0]) - 1\n",
    "\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "\n",
    "        #     if mid >= black_width:\n",
    "        #         right = mid - 1\n",
    "        #     else:\n",
    "        #         left = mid + 1\n",
    "\n",
    "        # width = left \n",
    "\n",
    "        return (width + 1) * (height + 1)\n",
    "\n",
    "    def find_black(self, image, x, y):\n",
    "        row = len(image) - 1\n",
    "        col = len(image[0]) - 1\n",
    "\n",
    "        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        height_max = 0\n",
    "        height_min = inf\n",
    "        width_max = 0\n",
    "        width_min = inf\n",
    "        q = deque()\n",
    "        q.append((x, y))\n",
    "\n",
    "        while q:\n",
    "            cur_x, cur_y = q.popleft()\n",
    "            height_max = max(cur_x, height_max)\n",
    "            height_min = min(cur_x, height_min)\n",
    "            width_max = max(cur_y, width_max)\n",
    "            width_min = min(cur_y, width_min)\n",
    "\n",
    "            for delta_x, delta_y in dirs:\n",
    "                x = cur_x + delta_x\n",
    "                y = cur_y + delta_y\n",
    "\n",
    "                if 0 <= x <= row and 0 <= y <= col and image[x][y] == '1':\n",
    "                    q.append((x, y))\n",
    "                    image[x][y] = '-1'\n",
    "\n",
    "        return height_max - height_min, width_max - width_min\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        # 二分法\n",
    "        # 基础是只在有必要的时候进行二分\n",
    "        # 需要四次二分，关键在于二分区间初始值的设定\n",
    "        m = len(image)\n",
    "        n = len(image[0])\n",
    "\n",
    "        # case1\n",
    "        left = 0\n",
    "        right = x\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            state = False \n",
    "            for element in image[mid]:\n",
    "                if element == \"1\": # 这一行存在1，\n",
    "                    state = True\n",
    "                    break \n",
    "            if state: # 这一行存在1，收缩right\n",
    "                right = mid - 1 # 收缩right,可能收缩过头，但是返回的是left所有没有关系\n",
    "            if not state: # 这一行不存在1，收缩left\n",
    "                left = mid + 1        \n",
    "        upLimit = left # \n",
    "\n",
    "        # case2\n",
    "        left = x\n",
    "        right = m-1\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            state = False \n",
    "            for element in image[mid]:\n",
    "                if element == \"1\": # 这一行存在1，收缩left  \n",
    "                    state = True \n",
    "                    break \n",
    "            if state: # 这一行存在1，收缩left\n",
    "                left = mid + 1\n",
    "            if not state:\n",
    "                right = mid - 1\n",
    "        downLimit = right\n",
    "\n",
    "        # case3\n",
    "        left = 0\n",
    "        right = y\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            state = False \n",
    "            for i in range(m):\n",
    "                if image[i][mid] == \"1\": # 这一列存在1，收缩right\n",
    "                    state = True \n",
    "                    break \n",
    "            if state:\n",
    "                right = mid - 1 # # 收缩right,可能收缩过头，但是返回的是left所有没有关系\n",
    "            if not state:\n",
    "                left = mid + 1\n",
    "        leftLimit = left \n",
    "\n",
    "        # case4\n",
    "        left = y\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            state = False \n",
    "            for i in range(m):\n",
    "                if image[i][mid] == \"1\": # 这一列存在1，收缩left \n",
    "                    state = True \n",
    "                    break \n",
    "            if state:\n",
    "                left = mid + 1\n",
    "            if not state:\n",
    "                right = mid - 1\n",
    "        rightLimit = right\n",
    "\n",
    "        # print(upLimit,downLimit,leftLimit,rightLimit)\n",
    "        return (abs(upLimit-downLimit)+1) * (abs(leftLimit-rightLimit)+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], X: int, Y: int) -> int:\n",
    "        M, N = len(image), len(image[0])\n",
    "\n",
    "        def hasBlack(x=None, y=None):\n",
    "            if y is None:\n",
    "                for j in range(N):\n",
    "                    if image[x][j] == '1':\n",
    "                        return True\n",
    "                return False\n",
    "            else:\n",
    "                for i in range(M):\n",
    "                    if image[i][y] == '1':\n",
    "                        return True\n",
    "                return False\n",
    "\n",
    "        lo, hi = 0, X\n",
    "        while lo <= hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if hasBlack(x=mid):\n",
    "                hi = mid - 1\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        minX = lo\n",
    "\n",
    "        lo, hi = 0, Y\n",
    "        while lo <= hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if hasBlack(y=mid):\n",
    "                hi = mid - 1\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        minY = lo\n",
    "\n",
    "\n",
    "        lo, hi = X, M-1\n",
    "        while lo <= hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if hasBlack(x=mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid -1 \n",
    "        maxX = hi\n",
    "\n",
    "        lo, hi = Y, N-1\n",
    "        while lo <= hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if hasBlack(y=mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid -1\n",
    "        maxY = hi\n",
    "\n",
    "        return (maxX-minX+1) * (maxY-minY+1)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    mid =  height / width = (row[-1] - row[0]) /(col[-1] - col[0])\n",
    "    left = 1\n",
    "    right = m / n \n",
    "    situation 1: if mid is too big, row[-1] - row[0] >= black height or col[-1] - col[0] >= black width\n",
    "    situation 2: if mid is too small,  row[-1] - row[0] < black height or col[-1] - col[0] < black width\n",
    "\n",
    "    '''\n",
    "    def BinarySearch(self, left, right, target, height, maximum, image):\n",
    "        \n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            target_list = [image[_][mid] for _ in range(len(image))] if not height else image[mid]\n",
    "\n",
    "            if (mid < target and '1'  not in target_list and not maximum):\n",
    "                left = mid + 1\n",
    "            elif ((mid <= target) or '1'  in target_list) and maximum:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return right if maximum else left\n",
    "\n",
    "\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        height_max = self.BinarySearch(0, len(image) - 1, x, True, True, image)\n",
    "\n",
    "        height_min = self.BinarySearch(0, len(image) - 1, x, True, False, image)\n",
    "\n",
    "        width_max = self.BinarySearch(0, len(image[0]) - 1, y, False, True, image)\n",
    "\n",
    "        width_min = self.BinarySearch(0, len(image[0]) - 1, y, False, False, image)\n",
    "\n",
    "        return (width_max - width_min + 1) * (height_max - height_min + 1)\n",
    "        # # find height max \n",
    "        # left = 0 \n",
    "        # right = len(image) - 1\n",
    "\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "\n",
    "        #     if mid <= x or '1'  in image[mid]:\n",
    "        #         left = mid + 1\n",
    "        #     else:\n",
    "        #         right = mid - 1\n",
    "        # height_max = right\n",
    "\n",
    "        # # find height min\n",
    "        # left = 0 \n",
    "        # right = len(image) - 1\n",
    "\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "\n",
    "        #     if mid < x and '1'  not in image[mid]:\n",
    "        #         left = mid + 1\n",
    "        #     else:\n",
    "        #         right = mid - 1\n",
    "\n",
    "        # height_min = left\n",
    "        \n",
    "        # # find width max\n",
    "        # left = 0\n",
    "        # right = len(image[0]) - 1\n",
    "\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "\n",
    "        #     y_list = [image[_][mid] for _ in range(len(image))]\n",
    "\n",
    "        #     if mid <= y or '1'  in y_list:\n",
    "        #         left = mid + 1\n",
    "        #     else:\n",
    "        #         right = mid - 1\n",
    "\n",
    "        # width_max = right\n",
    "\n",
    "        # left = 0\n",
    "        # right = len(image[0]) - 1\n",
    "\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "\n",
    "        #     y_list = [image[_][mid] for _ in range(len(image))]\n",
    "\n",
    "        #     if mid >= y or '1'  in y_list:\n",
    "        #         right = mid - 1\n",
    "        #     else:\n",
    "        #         left = mid + 1\n",
    "\n",
    "        # width_min = left\n",
    "\n",
    "        # return (width_max - width_min + 1) * (height_max - height_min + 1)\n",
    "         \n",
    "    #     # find black height\n",
    "    #     height, width = self.find_black(image, x, y)\n",
    "\n",
    "    #     # # # find height\n",
    "    #     # left = 0\n",
    "    #     # right = len(image) - 1 # row\n",
    "\n",
    "\n",
    "        \n",
    "    #     # height = left \n",
    "\n",
    "    #     # left = 0\n",
    "    #     # right = len(image[0]) - 1\n",
    "\n",
    "    #     # while left <= right:\n",
    "    #     #     mid = (left + right) // 2\n",
    "\n",
    "    #     #     if mid >= black_width:\n",
    "    #     #         right = mid - 1\n",
    "    #     #     else:\n",
    "    #     #         left = mid + 1\n",
    "\n",
    "    #     # width = left \n",
    "\n",
    "    #     return (width + 1) * (height + 1)\n",
    "\n",
    "    # def find_black(self, image, x, y):\n",
    "    #     row = len(image) - 1\n",
    "    #     col = len(image[0]) - 1\n",
    "\n",
    "    #     dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "    #     height_max = 0\n",
    "    #     height_min = inf\n",
    "    #     width_max = 0\n",
    "    #     width_min = inf\n",
    "    #     q = deque()\n",
    "    #     q.append((x, y))\n",
    "\n",
    "    #     while q:\n",
    "    #         cur_x, cur_y = q.popleft()\n",
    "    #         height_max = max(cur_x, height_max)\n",
    "    #         height_min = min(cur_x, height_min)\n",
    "    #         width_max = max(cur_y, width_max)\n",
    "    #         width_min = min(cur_y, width_min)\n",
    "\n",
    "    #         for delta_x, delta_y in dirs:\n",
    "    #             x = cur_x + delta_x\n",
    "    #             y = cur_y + delta_y\n",
    "\n",
    "    #             if 0 <= x <= row and 0 <= y <= col and image[x][y] == '1':\n",
    "    #                 q.append((x, y))\n",
    "    #                 image[x][y] = '-1'\n",
    "\n",
    "    #     return height_max - height_min, width_max - width_min\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        # 找到图像的上下左右边界并计算面积\n",
    "        up, down = self.find_up_and_down(image, x)\n",
    "        left, right = self.find_left_and_right(image, y)\n",
    "        return (down - up + 1) * (right - left + 1)\n",
    "        \n",
    "    def find_up_and_down(self, image, x):\n",
    "        # 找到图像的上下边界 m行 n列\n",
    "        m, n = len(image), len(image[0])\n",
    "        \n",
    "        def search_row(row):\n",
    "            for col in range(n):\n",
    "                if image[row][col] == \"1\":\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        # 二分查找上边界   \n",
    "        i, j = 0, x\n",
    "        while i + 1 < j:\n",
    "            mid = (i + j) // 2\n",
    "            if search_row(mid):\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid\n",
    "        up = i if search_row(i) else j\n",
    "        \n",
    "        # 二分查找下边界\n",
    "        i, j = x, m - 1\n",
    "        while i + 1 < j:\n",
    "            mid = (i + j) // 2\n",
    "            if search_row(mid):\n",
    "                i = mid\n",
    "            else:\n",
    "                j = mid\n",
    "        down = j if search_row(j) else i\n",
    "        \n",
    "        return up, down\n",
    "    \n",
    "    def find_left_and_right(self, image, y):\n",
    "        # 找到图像的左右边界\n",
    "        m, n = len(image), len(image[0])\n",
    "        \n",
    "        def search_col(col):\n",
    "            for row in range(m):\n",
    "                if image[row][col] == \"1\":\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        # 二分查找左边界 \n",
    "        i, j = 0, y\n",
    "        while i + 1 < j:\n",
    "            mid = (i + j) // 2\n",
    "            if search_col(mid):\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid\n",
    "        left = i if search_col(i) else j\n",
    "        \n",
    "        # 二分查找右边界\n",
    "        i, j = y, n - 1\n",
    "        while i + 1 < j:\n",
    "            mid = (i + j) // 2\n",
    "            if search_col(mid):\n",
    "                i = mid\n",
    "            else:\n",
    "                j = mid\n",
    "        right = j if search_col(j) else i\n",
    "        \n",
    "        return left, right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    mid =  height / width = (row[-1] - row[0]) /(col[-1] - col[0])\n",
    "    left = 1\n",
    "    right = m / n \n",
    "    situation 1: if mid is too big, row[-1] - row[0] >= black height or col[-1] - col[0] >= black width\n",
    "    situation 2: if mid is too small,  row[-1] - row[0] < black height or col[-1] - col[0] < black width\n",
    "\n",
    "    '''\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        # find height max \n",
    "        left = 0 \n",
    "        right = len(image) - 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            if mid <= x or '1'  in image[mid]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        height_max = right\n",
    "\n",
    "        # find height min\n",
    "        left = 0 \n",
    "        right = len(image) - 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            if mid >= x or '1'  in image[mid]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        height_min = left\n",
    "        \n",
    "        # find width max\n",
    "        left = 0\n",
    "        right = len(image[0]) - 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            y_list = [image[_][mid] for _ in range(len(image))]\n",
    "\n",
    "            if mid <= y or '1'  in y_list:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        width_max = right\n",
    "\n",
    "        left = 0\n",
    "        right = len(image[0]) - 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            y_list = [image[_][mid] for _ in range(len(image))]\n",
    "\n",
    "            if mid >= y or '1'  in y_list:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        width_min = left\n",
    "\n",
    "        return (width_max - width_min + 1) * (height_max - height_min + 1)\n",
    "         \n",
    "    #     # find black height\n",
    "    #     height, width = self.find_black(image, x, y)\n",
    "\n",
    "    #     # # # find height\n",
    "    #     # left = 0\n",
    "    #     # right = len(image) - 1 # row\n",
    "\n",
    "\n",
    "        \n",
    "    #     # height = left \n",
    "\n",
    "    #     # left = 0\n",
    "    #     # right = len(image[0]) - 1\n",
    "\n",
    "    #     # while left <= right:\n",
    "    #     #     mid = (left + right) // 2\n",
    "\n",
    "    #     #     if mid >= black_width:\n",
    "    #     #         right = mid - 1\n",
    "    #     #     else:\n",
    "    #     #         left = mid + 1\n",
    "\n",
    "    #     # width = left \n",
    "\n",
    "    #     return (width + 1) * (height + 1)\n",
    "\n",
    "    # def find_black(self, image, x, y):\n",
    "    #     row = len(image) - 1\n",
    "    #     col = len(image[0]) - 1\n",
    "\n",
    "    #     dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "    #     height_max = 0\n",
    "    #     height_min = inf\n",
    "    #     width_max = 0\n",
    "    #     width_min = inf\n",
    "    #     q = deque()\n",
    "    #     q.append((x, y))\n",
    "\n",
    "    #     while q:\n",
    "    #         cur_x, cur_y = q.popleft()\n",
    "    #         height_max = max(cur_x, height_max)\n",
    "    #         height_min = min(cur_x, height_min)\n",
    "    #         width_max = max(cur_y, width_max)\n",
    "    #         width_min = min(cur_y, width_min)\n",
    "\n",
    "    #         for delta_x, delta_y in dirs:\n",
    "    #             x = cur_x + delta_x\n",
    "    #             y = cur_y + delta_y\n",
    "\n",
    "    #             if 0 <= x <= row and 0 <= y <= col and image[x][y] == '1':\n",
    "    #                 q.append((x, y))\n",
    "    #                 image[x][y] = '-1'\n",
    "\n",
    "    #     return height_max - height_min, width_max - width_min\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "\n",
    "        m, n = len(image), len(image[0])\n",
    "\n",
    "        left = self.searchColumns(image, 0, y, 0, m, True)\n",
    "        right = self.searchColumns(image, y+1, n, 0, m, False)\n",
    "        top = self.searchRows(image, 0, x, left, right, True)\n",
    "        bottom = self.searchRows(image, x+1, m, left, right, False)\n",
    "        return (right - left) * (bottom - top)\n",
    "\n",
    "    \n",
    "    def searchColumns(self, image, i, j, top, bottom, white2balck):\n",
    "        while i != j:\n",
    "            k = top\n",
    "            mid = i + (j - i) // 2\n",
    "            while k < bottom and image[k][mid] == '0':\n",
    "                k += 1\n",
    "            if (k < bottom) == white2balck: # k < bottom 意味着 mid 列中有黑色像素\n",
    "                j = mid \n",
    "            else:\n",
    "                i = mid + 1\n",
    "\n",
    "        return i \n",
    "\n",
    "    def searchRows(self, image, i, j, left, right, white2balck):\n",
    "        while i != j:\n",
    "            k = left \n",
    "            mid = i + (j - i) // 2\n",
    "            while k < right and image[mid][k] == '0':\n",
    "                k += 1\n",
    "            if (k < right) == white2balck:\n",
    "                j = mid \n",
    "            else:\n",
    "                i = mid + 1\n",
    "\n",
    "        return i "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        # 四次二分\n",
    "        m=len(image)\n",
    "        n=len(image[0])\n",
    "        pos=[0,0,0,0]\n",
    "        left=0\n",
    "        right=x\n",
    "        while left<right:\n",
    "            mid=left+(right-left)//2\n",
    "            summ=sum(int(image[mid][i]) for i in range(n))\n",
    "            if summ>0:\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        pos[0]=left\n",
    "        left=x\n",
    "        right=m-1\n",
    "        while left<right:\n",
    "            mid=left+(right-left+1)//2\n",
    "            summ=sum(int(image[mid][i]) for i in range(n))\n",
    "            if summ>0:\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid-1\n",
    "        pos[2]=left\n",
    "        left=0\n",
    "        right=y\n",
    "        while left<right:\n",
    "            mid=left+(right-left)//2\n",
    "            summ=sum(int(image[i][mid]) for i in range(m))\n",
    "            if summ>0:\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        pos[1]=left\n",
    "        left=y\n",
    "        right=n-1\n",
    "        while left<right:\n",
    "            mid=left+(right-left+1)//2\n",
    "            summ=sum(int(image[i][mid]) for i in range(m))\n",
    "            if summ>0:\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid-1\n",
    "        pos[3]=left\n",
    "        return (pos[3]-pos[1]+1)*(pos[2]-pos[0]+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        m = len(image)\n",
    "        n = len(image[0])\n",
    "\n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        dirs = [1, 0, -1, 0, 1]\n",
    "\n",
    "        vis[x][y] = 1\n",
    "        q = [(x, y)]\n",
    "\n",
    "        left = right = y\n",
    "        top = bottom = x\n",
    "\n",
    "        while q:\n",
    "            nx, ny = q.pop(0)\n",
    "            for i in range(4):\n",
    "                dx = nx + dirs[i]\n",
    "                dy = ny + dirs[i + 1]\n",
    "                if not(0 <= dx < m)  or not(0 <= dy < n):\n",
    "                    continue\n",
    "                elif vis[dx][dy] == 0 and image[dx][dy] == \"1\":\n",
    "                    q.append((dx, dy))\n",
    "                    # print(dx, dy, image[dx][dy])\n",
    "                    # if image[dx][dy]:\n",
    "                    #     print(\"fuck\")\n",
    "                    vis[dx][dy] = 1\n",
    "                    left = min(dy, left)\n",
    "                    right = max(dy, right)\n",
    "                    top = max(dx, top)\n",
    "                    bottom = min(dx, bottom)\n",
    "                \n",
    "        \n",
    "        print(top, bottom, left, right)\n",
    "        return (top - bottom + 1) * (right - left + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        m, n = len(image), len(image[0])\n",
    "        up, down, left, right = x, x, y, y\n",
    "\n",
    "        def row(i):\n",
    "            for j in range(n):\n",
    "                if image[i][j] == '1':\n",
    "                    return True \n",
    "            return False \n",
    "        \n",
    "        def col(i):\n",
    "            for j in range(m):\n",
    "                if image[j][i] == '1':\n",
    "                    return True \n",
    "            return False\n",
    "\n",
    "        low, high = 0, x\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if row(mid):\n",
    "                up = mid \n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        \n",
    "        low, high = x, m - 1\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if row(mid):\n",
    "                down = mid \n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        \n",
    "        low, high = 0, y\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if col(mid):\n",
    "                left = mid \n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        \n",
    "        low, high = y, n - 1\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if col(mid):\n",
    "                right = mid \n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        \n",
    "        return (right - left + 1) * (down - up + 1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    mid =  height / width = (row[-1] - row[0]) /(col[-1] - col[0])\n",
    "    left = 1\n",
    "    right = m / n \n",
    "    situation 1: if mid is too big, row[-1] - row[0] >= black height or col[-1] - col[0] >= black width\n",
    "    situation 2: if mid is too small,  row[-1] - row[0] < black height or col[-1] - col[0] < black width\n",
    "\n",
    "    '''\n",
    "    def BinarySearch(self, left, right, target, height, maximum, image):\n",
    "        \n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            target_list = [image[_][mid] for _ in range(len(image))] if not height else image[mid]\n",
    "\n",
    "            if (mid < target and '1'  not in target_list and not maximum):\n",
    "                left = mid + 1\n",
    "            elif ((mid <= target) or '1'  in target_list) and maximum:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return right if maximum else left\n",
    "\n",
    "\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "\n",
    "        height_max = self.BinarySearch(0, len(image) - 1, x, True, True, image)\n",
    "        print(height_max)\n",
    "\n",
    "        height_min = self.BinarySearch(0, len(image) - 1, x, True, False, image)\n",
    "        print(height_min)\n",
    "\n",
    "        width_max = self.BinarySearch(0, len(image[0]) - 1, y, False, True, image)\n",
    "        print(width_max)\n",
    "\n",
    "        width_min = self.BinarySearch(0, len(image[0]) - 1, y, False, False, image)\n",
    "        print(width_min)\n",
    "\n",
    "        return (width_max - width_min + 1) * (height_max - height_min + 1)\n",
    "        # # find height max \n",
    "        # left = 0 \n",
    "        # right = len(image) - 1\n",
    "\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "\n",
    "        #     if mid <= x or '1'  in image[mid]:\n",
    "        #         left = mid + 1\n",
    "        #     else:\n",
    "        #         right = mid - 1\n",
    "        # height_max = right\n",
    "\n",
    "        # # find height min\n",
    "        # left = 0 \n",
    "        # right = len(image) - 1\n",
    "\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "\n",
    "        #     if mid < x and '1'  not in image[mid]:\n",
    "        #         left = mid + 1\n",
    "        #     else:\n",
    "        #         right = mid - 1\n",
    "\n",
    "        # height_min = left\n",
    "        \n",
    "        # # find width max\n",
    "        # left = 0\n",
    "        # right = len(image[0]) - 1\n",
    "\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "\n",
    "        #     y_list = [image[_][mid] for _ in range(len(image))]\n",
    "\n",
    "        #     if mid <= y or '1'  in y_list:\n",
    "        #         left = mid + 1\n",
    "        #     else:\n",
    "        #         right = mid - 1\n",
    "\n",
    "        # width_max = right\n",
    "\n",
    "        # left = 0\n",
    "        # right = len(image[0]) - 1\n",
    "\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "\n",
    "        #     y_list = [image[_][mid] for _ in range(len(image))]\n",
    "\n",
    "        #     if mid >= y or '1'  in y_list:\n",
    "        #         right = mid - 1\n",
    "        #     else:\n",
    "        #         left = mid + 1\n",
    "\n",
    "        # width_min = left\n",
    "\n",
    "        # return (width_max - width_min + 1) * (height_max - height_min + 1)\n",
    "         \n",
    "    #     # find black height\n",
    "    #     height, width = self.find_black(image, x, y)\n",
    "\n",
    "    #     # # # find height\n",
    "    #     # left = 0\n",
    "    #     # right = len(image) - 1 # row\n",
    "\n",
    "\n",
    "        \n",
    "    #     # height = left \n",
    "\n",
    "    #     # left = 0\n",
    "    #     # right = len(image[0]) - 1\n",
    "\n",
    "    #     # while left <= right:\n",
    "    #     #     mid = (left + right) // 2\n",
    "\n",
    "    #     #     if mid >= black_width:\n",
    "    #     #         right = mid - 1\n",
    "    #     #     else:\n",
    "    #     #         left = mid + 1\n",
    "\n",
    "    #     # width = left \n",
    "\n",
    "    #     return (width + 1) * (height + 1)\n",
    "\n",
    "    # def find_black(self, image, x, y):\n",
    "    #     row = len(image) - 1\n",
    "    #     col = len(image[0]) - 1\n",
    "\n",
    "    #     dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "    #     height_max = 0\n",
    "    #     height_min = inf\n",
    "    #     width_max = 0\n",
    "    #     width_min = inf\n",
    "    #     q = deque()\n",
    "    #     q.append((x, y))\n",
    "\n",
    "    #     while q:\n",
    "    #         cur_x, cur_y = q.popleft()\n",
    "    #         height_max = max(cur_x, height_max)\n",
    "    #         height_min = min(cur_x, height_min)\n",
    "    #         width_max = max(cur_y, width_max)\n",
    "    #         width_min = min(cur_y, width_min)\n",
    "\n",
    "    #         for delta_x, delta_y in dirs:\n",
    "    #             x = cur_x + delta_x\n",
    "    #             y = cur_y + delta_y\n",
    "\n",
    "    #             if 0 <= x <= row and 0 <= y <= col and image[x][y] == '1':\n",
    "    #                 q.append((x, y))\n",
    "    #                 image[x][y] = '-1'\n",
    "\n",
    "    #     return height_max - height_min, width_max - width_min\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        m = len(image)\n",
    "        n = len(image[0])\n",
    "\n",
    "        # find up most\n",
    "        up = 0\n",
    "        down = x\n",
    "        up_most = x\n",
    "\n",
    "        while up <= down:\n",
    "            mid = (up + down) // 2\n",
    "            inside = False\n",
    "            for j in range(n):\n",
    "                if image[mid][j] == '1':\n",
    "                    inside = True\n",
    "                    break\n",
    "            if inside:\n",
    "                up_most = mid\n",
    "                down = mid - 1\n",
    "            else:\n",
    "                up = mid + 1\n",
    "        \n",
    "        # find down most\n",
    "        up = x\n",
    "        down = m - 1\n",
    "        down_most = x\n",
    "\n",
    "        while up <= down:\n",
    "            mid = (up + down) // 2\n",
    "            inside = False\n",
    "            for j in range(n):\n",
    "                if image[mid][j] == '1':\n",
    "                    inside = True\n",
    "                    break\n",
    "            if inside:\n",
    "                down_most = mid\n",
    "                up = mid + 1\n",
    "            else:\n",
    "                down = mid - 1\n",
    "        \n",
    "        # find left most\n",
    "        left = 0\n",
    "        right = y\n",
    "        left_most = y\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            inside = False\n",
    "            for i in range(m):\n",
    "                if image[i][mid] == '1':\n",
    "                    inside = True\n",
    "                    break\n",
    "            if inside:\n",
    "                left_most = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        # find right most\n",
    "        left = y\n",
    "        right = n - 1\n",
    "        right_most = y\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            inside = False\n",
    "            for i in range(m):\n",
    "                if image[i][mid] == '1':\n",
    "                    inside = True\n",
    "                    break\n",
    "            if inside:\n",
    "                right_most = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        h = down_most - up_most + 1\n",
    "        w = right_most - left_most + 1\n",
    "\n",
    "        return h * w\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        m, n = len(image), len(image[0])\n",
    "        lb, ub = -1, x\n",
    "        while ub - lb > 1:\n",
    "            mid = (ub + lb) // 2\n",
    "            if any(image[mid][i] != '0' for i in range(n)):\n",
    "                ub = mid\n",
    "            else:\n",
    "                lb = mid\n",
    "        min_x = ub\n",
    "        lb, ub = x, m \n",
    "        while ub - lb > 1:\n",
    "            mid = (ub + lb) // 2\n",
    "            if any(image[mid][i] != '0' for i in range(n)):\n",
    "                lb = mid\n",
    "            else:\n",
    "                ub = mid\n",
    "        max_x = lb\n",
    "\n",
    "        lb, ub = -1, y\n",
    "        while ub - lb > 1:\n",
    "            mid = (ub + lb) // 2\n",
    "            print(lb, ub, mid)\n",
    "            if any(image[i][mid] != '0' for i in range(m)):\n",
    "                ub = mid\n",
    "            else:\n",
    "                lb = mid\n",
    "        min_y = ub\n",
    "        lb, ub = y, n\n",
    "        while ub - lb > 1:\n",
    "            mid = (ub + lb) // 2\n",
    "            print(lb, ub, mid)\n",
    "            if any(image[i][mid] != '0' for i in range(m)):\n",
    "                lb = mid\n",
    "            else:\n",
    "                ub = mid\n",
    "        max_y = lb\n",
    "        print(min_x, max_x, min_y, max_y)\n",
    "        return (max_x - min_x + 1) * (max_y - min_y + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\r\n",
    "        #遍历，更新  用roc坐标\r\n",
    "        Row, Col = len(image), len(image[0])\r\n",
    "\r\n",
    "        Up = x\r\n",
    "        Down = x\r\n",
    "        Left = y\r\n",
    "        Rgiht = y\r\n",
    "\r\n",
    "        for r in range(Row):\r\n",
    "            for c in range(Col):\r\n",
    "                if image[r][c] == '1':\r\n",
    "                    Up = min(Up, r)\r\n",
    "                    Down = max(Down, r)\r\n",
    "                    Left = min(Left, c)\r\n",
    "                    Rgiht = max(Rgiht, c)\r\n",
    "        \r\n",
    "        return (Down - Up + 1) * (Rgiht - Left + 1)\r\n",
    "        \r\n",
    "    def minArea2(self, image: List[List[str]], x: int, y: int) -> int:\r\n",
    "        #遍历，更新  用roc坐标\r\n",
    "        Row, Col = len(image), len(image[0])\r\n",
    "\r\n",
    "        Up = x\r\n",
    "        Down = x\r\n",
    "        Left = y\r\n",
    "        Rgiht = y\r\n",
    "\r\n",
    "        #------------- bfs + 记忆化\r\n",
    "        Q = collections.deque()\r\n",
    "        visited = [[False for _ in range(Col)] for _ in range(Row)]\r\n",
    "        Q.append((x, y))\r\n",
    "        visited[x][y] = True\r\n",
    "        while Q:\r\n",
    "            r, c = Q.popleft()\r\n",
    "\r\n",
    "            Up = min(Up, r)\r\n",
    "            Down = max(Down, r)\r\n",
    "            Left = min(Left, c)\r\n",
    "            Rgiht = max(Rgiht, c)\r\n",
    "\r\n",
    "            for nr, nc in [(r-1,c), (r+1,c), (r,c-1), (r,c+1)]:\r\n",
    "                if 0 <= nr < Row and 0 <= nc < Col:\r\n",
    "                    if visited[nr][nc] == False and image[nr][nc] == '1':\r\n",
    "                        visited[nr][nc] = True\r\n",
    "                        Q.append((nr, nc))\r\n",
    "        \r\n",
    "        return (Down - Up + 1) * (Rgiht - Left + 1)\r\n",
    "        \r\n",
    "    def minArea3(self, image: List[List[str]], x: int, y: int) -> int:\r\n",
    "        #遍历，更新  用roc坐标\r\n",
    "        Row, Col = len(image), len(image[0])\r\n",
    "\r\n",
    "        self.Up = x\r\n",
    "        self.Down = x\r\n",
    "        self.Left = y\r\n",
    "        self.Rgiht = y\r\n",
    "\r\n",
    "        #------------- dfs + 记忆化\r\n",
    "        visited = [[False for _ in range(Col)] for _ in range(Row)]\r\n",
    "        \r\n",
    "        def dfs(r: int, c: int) -> None:\r\n",
    "            self.Up = min(self.Up, r)\r\n",
    "            self.Down = max(self.Down, r)\r\n",
    "            self.Left = min(self.Left, c)\r\n",
    "            self.Rgiht = max(self.Rgiht, c)\r\n",
    "\r\n",
    "            for nr, nc in [(r-1,c), (r+1,c), (r,c-1), (r,c+1)]:\r\n",
    "                if 0 <= nr < Row and 0 <= nc < Col:\r\n",
    "                    if visited[nr][nc] == False and image[nr][nc] == '1':\r\n",
    "                        visited[nr][nc] = True\r\n",
    "                        dfs(nr, nc)\r\n",
    "\r\n",
    "        visited[x][y] = True\r\n",
    "        dfs(x, y)\r\n",
    "        return (self.Down - self.Up + 1) * (self.Rgiht - self.Left + 1)\r\n",
    "        \r\n",
    "    def minArea4(self, image: List[List[str]], x: int, y: int) -> int:\r\n",
    "        #遍历，更新  用roc坐标\r\n",
    "        Row, Col = len(image), len(image[0])\r\n",
    "\r\n",
    "        lo, hi = 0, x\r\n",
    "        while lo < hi:\r\n",
    "            mid = (lo + hi) // 2\r\n",
    "            c = 0\r\n",
    "            while c < Col and image[mid][c] == '0':     c += 1\r\n",
    "            if c < Col:\r\n",
    "                hi = mid\r\n",
    "            else:\r\n",
    "                lo = mid + 1\r\n",
    "        Up = lo\r\n",
    "\r\n",
    "        lo, hi = x, Row - 1\r\n",
    "        while lo < hi:\r\n",
    "            mid = (lo + hi + 1) // 2\r\n",
    "            c = 0\r\n",
    "            while c < Col and image[mid][c] == '0':    c += 1\r\n",
    "            if c < Col:\r\n",
    "                lo = mid \r\n",
    "            else:\r\n",
    "                hi = mid - 1\r\n",
    "        Down = lo\r\n",
    "\r\n",
    "        lo, hi = 0, y\r\n",
    "        while lo < hi:\r\n",
    "            mid = (lo + hi) // 2\r\n",
    "            r = 0\r\n",
    "            while r < Row and image[r][mid] == '0':    r += 1\r\n",
    "            if r < Row:\r\n",
    "                hi = mid\r\n",
    "            else:\r\n",
    "                lo = mid + 1\r\n",
    "        Left = lo\r\n",
    "\r\n",
    "        lo, hi = y, Col - 1\r\n",
    "        while lo < hi:\r\n",
    "            mid = (lo + hi + 1) // 2\r\n",
    "            r = 0\r\n",
    "            while r < Row and image[r][mid] == '0':    r += 1\r\n",
    "            if r < Row:\r\n",
    "                lo = mid\r\n",
    "            else:\r\n",
    "                hi = mid - 1\r\n",
    "        Right = lo\r\n",
    "\r\n",
    "        return (Down - Up + 1) * (Right - Left + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        m, n = len(image), len(image[0])\n",
    "        lb, ub = -1, x\n",
    "        while ub - lb > 1:\n",
    "            mid = (ub + lb) // 2\n",
    "            if any(image[mid][i] == '1' for i in range(n)):\n",
    "                ub = mid\n",
    "            else:\n",
    "                lb = mid\n",
    "        min_x = ub\n",
    "        lb, ub = x, m \n",
    "        while ub - lb > 1:\n",
    "            mid = (ub + lb) // 2\n",
    "            if any(image[mid][i] == '1' for i in range(n)):\n",
    "                lb = mid\n",
    "            else:\n",
    "                ub = mid\n",
    "        max_x = lb\n",
    "\n",
    "        lb, ub = -1, y\n",
    "        while ub - lb > 1:\n",
    "            mid = (ub + lb) // 2\n",
    "            print(lb, ub, mid)\n",
    "            if any(image[i][mid] == '1' for i in range(m)):\n",
    "                ub = mid\n",
    "            else:\n",
    "                lb = mid\n",
    "        min_y = ub\n",
    "        lb, ub = y, n\n",
    "        while ub - lb > 1:\n",
    "            mid = (ub + lb) // 2\n",
    "            print(lb, ub, mid)\n",
    "            if any(image[i][mid] == '1' for i in range(m)):\n",
    "                lb = mid\n",
    "            else:\n",
    "                ub = mid\n",
    "        max_y = lb\n",
    "        print(min_x, max_x, min_y, max_y)\n",
    "        return (max_x - min_x + 1) * (max_y - min_y + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        minx, miny, maxx, maxy = x, y, x, y\n",
    "        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        m, n = len(image), len(image[0])\n",
    "\n",
    "        q = [(x, y)]\n",
    "        vis = set()\n",
    "        vis.add((x, y))\n",
    "\n",
    "        while q:\n",
    "            i, j = q.pop(0)\n",
    "            minx = min(minx, i)\n",
    "            miny = min(miny, j)\n",
    "            maxx = max(maxx, i)\n",
    "            maxy = max(maxy, j)\n",
    "            for k in range(4):\n",
    "                di, dj = i + dirs[k][0], j + dirs[k][1]\n",
    "                if 0 <= di < m and 0 <= dj < n:\n",
    "                    if (di, dj) not in vis and image[di][dj] == \"1\":\n",
    "                        q.append((di, dj))\n",
    "                        vis.add((di, dj))\n",
    "        return (maxx - minx + 1) * (maxy - miny + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        m = len(image)\n",
    "        n = len(image[0])\n",
    "        edge = [x,x,y,y] # Up Down Left Right\n",
    "        q = deque()\n",
    "        q.append((x,y))\n",
    "        visited = {(x,y),}\n",
    "        directions = ((0,1),(1,0),(0,-1),(-1,0))\n",
    "        k_list = (0,1,2,3)\n",
    "        while len(q):\n",
    "            now = q.popleft()\n",
    "            for k in k_list:\n",
    "                x = now[0] + directions[k][0]\n",
    "                y = now[1] + directions[k][1]\n",
    "                t = (x,y)\n",
    "                if x >= m or x < 0 or y >= n or y < 0 or t in visited or image[x][y] != '1':\n",
    "                    continue\n",
    "                edge = [min(edge[0],x),max(edge[1],x),min(edge[2], y), max(edge[3],y)]\n",
    "                visited.add(t)\n",
    "                q.append(t)\n",
    "        return (edge[1] - edge[0]+1) * (edge[3] - edge[2]+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        \n",
    "        m = len(image)\n",
    "        n = len(image[0])\n",
    "        edge = [x,x,y,y] # Up Down Left Right\n",
    "        q = deque()\n",
    "        q.append((x,y))\n",
    "        visited = {(x,y),}\n",
    "        directions = ((0,1),(1,0),(0,-1),(-1,0))\n",
    "        k_list = (0,1,2,3)\n",
    "        while len(q):\n",
    "            now = q.popleft()\n",
    "            for k in k_list:\n",
    "                x = now[0] + directions[k][0]\n",
    "                y = now[1] + directions[k][1]\n",
    "                t = (x,y)\n",
    "                if x >= m or x < 0 or y >= n or y < 0 or t in visited or image[x][y] != '1':\n",
    "                    continue\n",
    "                edge = [min(edge[0],x),max(edge[1],x),min(edge[2], y), max(edge[3],y)]\n",
    "                visited.add(t)\n",
    "                q.append(t)\n",
    "        return (edge[1] - edge[0]+1) * (edge[3] - edge[2]+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        result=1\n",
    "        x_lst=[]\n",
    "        y_lst=[]\n",
    "        def dfs(image,x,y,x_lst,y_lst):\n",
    "            if x<0 or x>=len(image) or y<0 or y>=len(image[0]) or image[x][y]!='1':\n",
    "                return \n",
    "            image[x][y]='-1'\n",
    "            x_lst.append(x)\n",
    "            y_lst.append(y)\n",
    "            dfs(image,x-1,y,x_lst,y_lst)\n",
    "            dfs(image,x+1,y,x_lst,y_lst)\n",
    "            dfs(image,x,y+1,x_lst,y_lst)\n",
    "            dfs(image,x,y-1,x_lst,y_lst)\n",
    "\n",
    "            return (max(x_lst)-min(x_lst)+1)*(max(y_lst)-min(y_lst)+1)\n",
    "        return dfs(image,x,y,x_lst,y_lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        \n",
    "        directions = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        m,n = len(image),len(image[0])\n",
    "        self.l, self.r, self.b, self.u = n, -3, m, -3\n",
    "        def dfs(i,j):\n",
    "            print(self.l,self.r,self.b,self.u)\n",
    "            self.l,self.r,self.b,self.u = min(self.l,j),max(self.r,j),min(self.b,i),max(self.u,i)\n",
    "            image[i][j] = 0\n",
    "            print(i,j)\n",
    "            print(self.l,self.r,self.b,self.u)\n",
    "            for direction in directions:\n",
    "                new_i, new_j = i+direction[0], j+direction[1]\n",
    "                if 0<=new_i<m and 0<=new_j<n and image[new_i][new_j]=='1':\n",
    "                    dfs(new_i,new_j)\n",
    "                    \n",
    "     \n",
    "        dfs(x, y)\n",
    "        return (self.r-self.l+1)*(self.u-self.b+1) if (self.r-self.l+1)*(self.u-self.b+1)>0 else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        \n",
    "        directions = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        m,n = len(image),len(image[0])\n",
    "        self.l, self.r, self.b, self.u = n, -3, m, -3\n",
    "        def dfs(i,j):\n",
    "            #print(self.l,self.r,self.b,self.u)\n",
    "            self.l,self.r,self.b,self.u = min(self.l,j),max(self.r,j),min(self.b,i),max(self.u,i)\n",
    "            image[i][j] = 0\n",
    "            for direction in directions:\n",
    "                new_i, new_j = i+direction[0], j+direction[1]\n",
    "                if 0<=new_i<m and 0<=new_j<n and image[new_i][new_j]=='1':\n",
    "                    dfs(new_i,new_j)\n",
    "                    \n",
    "     \n",
    "        dfs(x, y)\n",
    "        return (self.r-self.l+1)*(self.u-self.b+1) if (self.r-self.l+1)*(self.u-self.b+1)>0 else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        \n",
    "        directions = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        m,n = len(image),len(image[0])\n",
    "        self.l, self.r, self.b, self.u = n, -3, m, -3\n",
    "        def dfs(i,j):\n",
    "            #print(self.l,self.r,self.b,self.u)\n",
    "            self.l,self.r,self.b,self.u = min(self.l,j),max(self.r,j),min(self.b,i),max(self.u,i)\n",
    "            image[i][j] = 0\n",
    "            for direction in directions:\n",
    "                new_i, new_j = i+direction[0], j+direction[1]\n",
    "                if 0<=new_i<m and 0<=new_j<n and image[new_i][new_j]=='1':\n",
    "                    dfs(new_i,new_j)\n",
    "        dfs(x, y)\n",
    "        return (self.r-self.l+1)*(self.u-self.b+1) if (self.r-self.l+1)*(self.u-self.b+1)>0 else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minArea(self, image: List[List[str]], x: int, y: int) -> int:\n",
    "        \n",
    "        directions = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        m,n = len(image),len(image[0])\n",
    "        self.l, self.r, self.b, self.u = n, -3, m, -3\n",
    "        def dfs(i,j):\n",
    "            #print(self.l,self.r,self.b,self.u)\n",
    "            self.l,self.r,self.b,self.u = min(self.l,j),max(self.r,j),min(self.b,i),max(self.u,i)\n",
    "            image[i][j] = 0\n",
    "            for direction in directions:\n",
    "                new_i, new_j = i+direction[0], j+direction[1]\n",
    "                if 0<=new_i<m and 0<=new_j<n and image[new_i][new_j]=='1':\n",
    "                    dfs(new_i,new_j)\n",
    "                    \n",
    "     \n",
    "        dfs(x, y)\n",
    "        return (self.r-self.l+1)*(self.u-self.b+1) if (self.r-self.l+1)*(self.u-self.b+1)>0 else 0\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
